\chapter{Вопрос № 10}

Построение решений рекуррентных соотношений с постоянными коэффициентами с помощью обыкновенных производящих функций.

\section{Неоднородные рекуррентные соотношения}

Рассмотрим пример $$ a_{n+1} = 4a_n - 100 $$, при начальных условиях
\[
	a_0 = 50
\]
Преобразуем его следующим образом:
\[
	x^{n+1}a_{n+1} = 4x^{n+1}a_n - 100 x^{n+1}
\]
и просуммируем по всем $n$ от 0:
\[
	\sum_{n=0}^{\infty}x^{n+1}a_{n+1} = 4x\sum_{n=0}^\infty x^na_n - 100 x\sum_{n=0}^\infty x^{n}
\]
тогда если положить, что $f\left(x\right)$ - опф для искомой последовательности, тогда выражение преобразуется следующим образом:
\[
	f\left(x\right) - a_0 = 4xf\left(x\right) - \frac{100 x}{1 - x}
\]
выражаем $f\left(x\right)$:
\[
	f\left(x\right) = \frac{a_0}{1-4x} - \frac{100x}{\left(1-x\right)\left(1-4x\right)}
\]
раскладываем на простейшие правую часть:
\[
	\frac{x}{\left(1-x\right)\left(1-4x\right)} = \frac{A}{1-x} + \frac{B}{1-4x} = \frac{1/3}{1-x} - \frac{1/3}{1-4x}
\]
собирая все вместе получаем:
\[
	f\left(x\right) = \sum_{n=0}^\infty a_n x^n = a_0\sum_{n=0}^\infty 4^n x^n - \frac{100}{3}\left(\sum_{n=0}^{\infty} \left(4^n-1\right) x^n \right)
\]

Похожим образом омжно построить решения для линейных рекуррентных соотношений с постоянными коэффициентами и большего порядка. Для рекуррентных соотношений с переменными коэффициентами такое решение уже не подходит.
